Đặt G là một đồ thị có trọng số liên thông. Trong mỗi bước, thuật toán Prim chọn một cạnh nối một đồ thị con với một đỉnh không thuộc đồ thị con đó. Vì G liên thông nên luôn tồn tại đường đi từ mỗi đồ thị con tới tất cả các đỉnh còn lại. Kết quả T của thuật toán Prim là một cây, vì các cạnh và đỉnh được thêm vào T là liên thông và cạnh mới thêm không bao giờ tạo thành chu trình với các cạnh cũ. Đặt T1 là một cây bao trùm nhỏ nhất của G. Nếu T1=T thì T là cây bao trùm nhỏ nhất. Nếu không, đặt e là cạnh đầu tiên được thêm vào T mà không thuộc T1, và V là tập hợp các đỉnh thuộc T trước khi thêm e. Một đầu của e thuộc V và đầu kia không thuộc V. Vì T1 là một cây bao trùm của G, nên tồn tại đường đi trong T1 nối hai đầu của e. Trên đường đi đó, nhất định tồn tại cạnh f nối một đỉnh trong V với một đỉnh ngoài V. Trong bước lặp khi e được thêm vào Y, thuật toán cũng có thể chọn f thay vì e nếu như trọng số của nó nhỏ hơn e. Vì f không được chọn nên

Đặt T2 là đồ thị thu được bằng cách xóa f và thêm e vào T1. Dễ thấyT2 liên thông, có cùng số cạnh như T1, và tổng trọng số các cạnh không quá trọng số của T1, nên nó cũng là một cây bao trùm nhỏ nhất của G và nó chứa e cũng như tất cả các cạnh được thuật toán chọn trước nó. Lặp lại lập luận trên nhiều lần, cuối cùng ta thu được một cây bao trùm nhỏ nhất của G giống hệt như T. Vì vậy T là một cây bao trùm nhỏ nhất.